import java.util.Stack;

class Solution {
    public String decodeString(String _s) {
        char[] s = _s.toCharArray();
        Stack<StringBuffer> st = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        st.push(new StringBuffer(""));
        int i = 0;
        int tmp = 0;
        StringBuffer str = new StringBuffer();
        while (i < s.length) {
            if (s[i] >= '0' && s[i] <= '9') {
                while (i < s.length && s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(tmp);
                tmp = 0;
            } else if (s[i] == '[') {
                i++;
                while (i < s.length && s[i] >= 'a' && s[i] <= 'z') {
                    str.append(s[i]);
                    i++;
                }
                st.push(str);
                str = new StringBuffer();
            } else if (s[i] == ']') {
                //解析字符串
                int k = nums.pop();
                StringBuffer str1 = st.pop();
                StringBuffer str2 = new StringBuffer();
                while (k-- > 0) {
                    str2.append(str1);
                }
                st.push(st.pop().append(str2));
                i++;
            } else {
                while (i < s.length && s[i] >= 'a' && s[i] <= 'z') {
                    str.append(s[i]);
                    i++;
                }
                st.push(st.pop().append(str));
                str = new StringBuffer();
            }
        }
        return st.pop().toString();
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length) return false;
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0, n = pushed.length;
        while (i < n && j < n) {
            if(i < n && j < n && !stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }else if(i < n && j < n && pushed[i] != popped[j]) {
                stack.push(pushed[i]);
                i++;
            }else if(i < n && j < n && pushed[i] == popped[j]) {
                i++;j++;
            }
        }
        while(j < n && stack.peek() == popped[j]) {
            stack.pop();
            j++;
        }
        return stack.isEmpty();
    }
}

public class Test {
    public static void main(String[] args) {
        int[] nums1 = {2,3,0,1};
        int[] nums2 = {0,3,2,1};
        boolean ret = new Solution().validateStackSequences(nums1,nums2);
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        String ret = new Solution().decodeString("3[a2[c]]");
        System.out.println(ret);
    }
}


















